package com.test.daily.leetcode.y2022.m07.day0707.v01;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/7/7 上午 10:26
 * @version: 1.0
 */
public class Solution {
    public void mergrSorted(int[] arr) {

    }

    public int process(int[] arr, int L, int R) {
        int M = L + ((R - L) >> 1);
        return process(arr, L, M)
                + process(arr, M + 1, R)
        + merge(arr, L, M, R);
    }

    public int merge(int[] arr, int L, int M, int R) {
        int[] help = new int[R - L + 1];
        int p1 = L, p2 = M + 1;
        int i = 0;
        int ans = 0;
        while (p1 <= M && p2 <= R) {
            ans += arr[p1] < arr[p2]? (R - p2 + 1)*arr[p2] : 0;
            help[i] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= M) {
            arr[i++] = arr[p1++];
        }
        while (p2 <= R) {
            help[i++] = arr[p2++];
        }
        i = 0;
        for (; i < help.length; i++) {
            arr[L + i] = help[i++];
        }
        return ans;
    }
}
